//题解链接：https://leetcode.cn/problems/0ynMMM/solutions/2253433/jian-zhi-offer-ii-039-zhi-fang-tu-zui-da-jr35/
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution
{
public:
    //思路 对于每一个节点都找以它为中心左右能延申多少 利用单调栈O(N)就能完成
    //单调栈: 栈里永远是递增的,意味着栈顶的下一个元素就是上一个比它小的
    //1.遍历数组
    //2.针对每一个元素,如果它比栈顶元素小,此时说明他是栈顶元素往右边扩散的终点,
    //   而栈顶元素往左边扩散的终点就是栈里的下一个元素(栈里永远是递增的,意味着栈顶的下一个元素就是上一个比栈顶元素小的)
    //   拿到左右边界,计算面积后出栈更新答案
    stack<int> st;
    //传入右端点
    int get_area(vector<int> &heights, int end)
    {
        //栈顶的值 
        int value = heights[st.top()];
        st.pop();
        //左端点
        int begin = st.empty() ? 0 : st.top() + 1;
        //计算 以栈顶向两边扩散的最大面积
        int area = (end - begin) * value;
        return area;
    }
    int largestRectangleArea(vector<int> &heights)
    {
        int res = 0;
        //遍历数组
        for (int i = 0; i < heights.size(); i++)
        {
            //如果遇到栈顶的右端点
            while ((!st.empty()) && heights[st.top()] > heights[i])
            {
                //更新答案
                res = max(get_area(heights, i), res);
            }
            //因为他前面所有比它大的元素的右端点,已经计算完并出栈
            //此时它下一个元素就是上一个比它小的,也就是它的左端点
            //把当前元素入栈寻找其左端点
            st.push(i);
        }
        while (!st.empty())
        {
            res = max(get_area(heights, heights.size()), res);
        }
        return res;
    }
};